/*
 * Author: 王迪 1300012802
 *
 * Outline:
 * 对于每个询问，枚举每个合法的人，从他出发进行广搜，
 * 计算出他到其余人之间的最短距离，并计算紧密中心度。
 * 复杂度O(num_query * num_person * (num_person + num_relation))，
 *
 * Optimization:
 * 加了一个剪枝：即在广搜过程中，把剩余未访问的点都按照
 * 最小的可能距离计算，如果这样得出的紧密中心度不足以进入我们的
 * 考虑范围，则不用再进行剩下的广搜。这需要实现一个并查集，
 * 来计算每个联通块的大小。
 *
 * Performance:
 * 实现得比较粗犷，10k数据大概要1分钟。
 */
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <utility>
#include <functional>
#include <unordered_map>
#include <unordered_set>

using namespace std;

vector<string> splitString(const string &src, char delimeter) 
{
    vector<string> res;
    string tmp = "";
    for (int i = 0; i < (int)src.size(); ++ i) 
    {
        if (src[i] == delimeter) 
        {
            if (tmp.size() > 0) res.push_back(tmp);
            tmp = "";
        }
        else
        {
            tmp += src[i];
        }
    }
    if (tmp.size() > 0) res.push_back(tmp);
    return res;
}

inline int stringToInt(const string &src)
{
    return atoi(src.c_str());
}

unordered_map<int, int> person_id_to_axis;
vector<int> person_axis;
unordered_map<string, int> tags_name_to_id;
unordered_map<int, unordered_set<int>> forum_has_tags;
vector<unordered_set<int>> person_joins_forums;
vector<unordered_set<int>> person_knows_persons;

void readNetworkData(const string &data_path)
{
    char buf[BUFSIZ];

    string person_data_file = data_path + "person.csv";
    person_id_to_axis.clear();
    FILE *f_person = fopen(person_data_file.c_str(), "r");
    fgets(buf, BUFSIZ, f_person);
    while (fgets(buf, BUFSIZ, f_person)) {
        static int axis_index = 0;
        vector<string> parts = splitString(string(buf), '|');
        person_id_to_axis[stringToInt(parts[0])] = axis_index;
        ++ axis_index;
    }
    person_axis.resize(person_id_to_axis.size());
    for (const auto &v : person_id_to_axis) person_axis[v.second] = v.first;

    string tag_data_file = data_path + "tag.csv";
    tags_name_to_id.clear();
    FILE *f_tag = fopen(tag_data_file.c_str(), "r");
    fgets(buf, BUFSIZ, f_tag);
    while (fscanf(f_tag, "%s", buf) != EOF)
    {
        vector<string> parts = splitString(string(buf), '|');
        tags_name_to_id[parts[1]] = stringToInt(parts[0]);
    }
    fclose(f_tag);

    string forum_has_tag_data_file = data_path + "forum_hasTag_tag.csv";
    forum_has_tags.clear();
    FILE *f_forum_has_tag = fopen(forum_has_tag_data_file.c_str(), "r");
    fgets(buf, BUFSIZ, f_forum_has_tag);
    while (fscanf(f_forum_has_tag, "%s", buf) != EOF)
    {
        vector<string> parts = splitString(string(buf), '|');
        forum_has_tags[stringToInt(parts[0])].insert(stringToInt(parts[1]));
    }
    fclose(f_forum_has_tag);

    string forum_has_member_data_file = data_path + "forum_hasMember_person.csv";
    person_joins_forums.clear();
    person_joins_forums.resize(person_id_to_axis.size());
    FILE *f_forum_has_member = fopen(forum_has_member_data_file.c_str(), "r");
    fgets(buf, BUFSIZ, f_forum_has_member);
    while (fscanf(f_forum_has_member, "%s", buf) != EOF)
    {
        vector<string> parts = splitString(string(buf), '|');
        person_joins_forums[person_id_to_axis[stringToInt(parts[1])]].insert(stringToInt(parts[0]));
    }
    fclose(f_forum_has_member);

    string person_knows_person_data_file = data_path + "person_knows_person.csv";
    person_knows_persons.clear();
    person_knows_persons.resize(person_id_to_axis.size());
    FILE *f_person_knows_person = fopen(person_knows_person_data_file.c_str(), "r");
    fgets(buf, BUFSIZ, f_person_knows_person);
    while (fscanf(f_person_knows_person, "%s", buf) != EOF)
    {
        vector<string> parts = splitString(string(buf), '|');
        person_knows_persons[person_id_to_axis[stringToInt(parts[0])]].insert(person_id_to_axis[stringToInt(parts[1])]);
        person_knows_persons[person_id_to_axis[stringToInt(parts[1])]].insert(person_id_to_axis[stringToInt(parts[0])]);
    }
}

pair<bool, double> calculateClosenessCentrality(int p, int cnt_vrtx, double bound, const unordered_set<int> &valid_persons, unordered_map<int, unordered_set<int>> &person_knows_persons)
{
    if (cnt_vrtx == 1)
    {
        return make_pair(false, 0.0);
    }
    -- cnt_vrtx;
    queue<int> q;
    vector<int> dist(person_id_to_axis.size(), -1);
    q.push(p);
    dist[p] = 0;
    int sum_dist = 0;
    int q_length = 0;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        int dist_u = dist[u];
        unordered_set<int> &knows_persons = person_knows_persons[u];
        for (int v : knows_persons)
        {
            if (dist[v] < 0)
            {
                int dist_v = dist_u + 1;
                dist[v] = dist_v;
                q.push(v);
                sum_dist += dist_v;
                ++ q_length;
            }
        }
        if ((double)cnt_vrtx * cnt_vrtx / (sum_dist + (cnt_vrtx - q_length) * (dist_u + 1)) < bound) return make_pair(false, 0.0);
    }
    return make_pair(true, (double)cnt_vrtx * cnt_vrtx / sum_dist);
}

void evaluateValidPersons(const string &tag, unordered_set<int> &des, unordered_map<int, unordered_set<int>> &graph)
{
    des.clear();
    graph.clear();
    int tag_id = tags_name_to_id[tag];
    int axis_cnt = person_axis.size();
    for (int p = 0; p < axis_cnt; ++ p)
    {
        auto &joins_forums = person_joins_forums[p];
        for (int f : joins_forums)
        {
            if (forum_has_tags[f].count(tag_id) > 0)
            {
                des.insert(p);
                break;
            }
        }
    }
    for (int p : des) 
    {
        unordered_set<int> &knows_persons = person_knows_persons[p];
        unordered_set<int> &filtered = graph[p];
        if (knows_persons.size() < des.size())
        {
            for (int v : knows_persons)
            {
                if (des.count(v) == 0) continue;
                filtered.insert(v);
            }
        }
        else
        {
            for (int v : des)
            {
                if (knows_persons.count(v) == 0) continue;
                filtered.insert(v);
            }
        }
    }
}

struct DisjointSet 
{
    vector<int> root, size;
    DisjointSet(int axis_cnt) 
    {
        root.resize(axis_cnt);
        size.resize(axis_cnt, 1);
        for (int i = 0; i < axis_cnt; ++ i)
        {
            root[i] = i;
        }
    }
    int getRoot(int x) 
    {
        return (x == root[x] ? x : root[x] = getRoot(root[x]));
    }
    void merge(int x, int y) 
    {
        x = getRoot(x);
        y = getRoot(y);
        if (x != y) 
        {
            if (size[x] > size[y]) swap(x, y);
            root[x] = y;
            size[y] += size[x];
        }
    }
};

void evaluatePersonBelongBlockSize(const unordered_set<int> &valid_persons, vector<int> &belong_block_size, unordered_map<int, unordered_set<int>> &person_knows_persons) 
{
    int axis_cnt = person_axis.size();
    DisjointSet ds(axis_cnt);
    for (int p : valid_persons)
    {
        unordered_set<int> &knows_persons = person_knows_persons[p];
        for (int v : knows_persons)
        {
            ds.merge(p, v);
        }
    }
    for (int p : valid_persons)
    {
        belong_block_size[p] = ds.size[ds.getRoot(p)];
    }
}

int main(int argc, char *argv[]) 
{
#ifndef LOCAL
    string data_path(argv[1]);
    int data_size = atoi(argv[2]);
    string query_file(argv[3]);
    string answer_file(argv[4]);
#else
    string data_path("../../../data/10k-network/");
    int data_size = 10000;
    string query_file("../query4.in");
    string answer_file("../query4.out");
#endif

    readNetworkData(data_path);

    FILE *f_query = fopen(query_file.c_str(), "r");
    FILE *f_answer = fopen(answer_file.c_str(), "w");

    int k;
    char buf[BUFSIZ];

    priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> heap;
    unordered_set<int> valid_persons;
    unordered_map<int, unordered_set<int>> valid_person_knows_persons;

    while (fscanf(f_query, "%d%s", &k, buf) != EOF) 
    {
        string tag(buf);
        evaluateValidPersons(tag, valid_persons, valid_person_knows_persons);
        
        vector<int> belong_block_size(person_axis.size(), 0);
        evaluatePersonBelongBlockSize(valid_persons, belong_block_size, valid_person_knows_persons);

        for (int p : valid_persons)
        {
            double bound = 0.0;
            if ((int)heap.size() == k) bound = heap.top().first;
            pair<bool, double> closeness_centrality = calculateClosenessCentrality(p, belong_block_size[p], bound, valid_persons, valid_person_knows_persons);
            if (closeness_centrality.first)
            {
                heap.push(make_pair(closeness_centrality.second, -person_axis[p]));
                if ((int)heap.size() > k) 
                {
                    heap.pop();
                }
            }
        }
        
        vector<pair<double,int>> ans;
        while (heap.size()) {
            ans.push_back(heap.top());
            heap.pop();
        }
        reverse(begin(ans), end(ans));

        for (const auto &v : ans) fprintf(f_answer, "%d ", -v.second);
        fprintf(f_answer, "\n");
    }

    fclose(f_query);
    fclose(f_answer);
    
    return 0;
}
